package com.cuz.hot100;

import com.cuz.daileetcode.utils.ArrayUtils;

import java.util.AbstractList;
import java.util.Arrays;

public class Q60getPermutation {

    // int[index]表示index的阶乘值
    private static int[] f(int n) {
        int[] dp = new int[n+1];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1] * (i);
        }
        return dp;
    }

    /***
     * 123
     * 132
     * 213
     * 231
     * 312
     * 321
     * n=3 k=3
     * 1开头2个f（n-1）=2个
     * 3/2=1 用 allCanUse中的第1+1个
     *
     * @param n
     * @param k
     * @return
     */
    public static String getPermutation1(int n, int k) {
        if (n <= 0 || k <= 0) {
            return "";
        }
        int[] f = f(n);
        StringBuilder res = new StringBuilder();
        int[]allCanUse=new int[n];
        for (int i = 0; i < n; i++) {
            allCanUse[i]=i+1;
        }
        //当前是第几个阶乘 第一个数 第n-1阶乘
        int curF=n-1;
        k--;
        for (int i = 1; i <= n; i++) {
            //3-1-1==>f[1]=2的阶乘
            int shouldUse=k/(f[curF]);
            int value = findFirstCanUse(allCanUse, shouldUse+1);
            res.append(value);
            k=k%f[curF--];
        }
        return res.toString();
    }
    private static int findFirstCanUse(int[]allCanUse,int i){
        for (int index = 0; index < allCanUse.length; index++) {
            if (allCanUse[index]>0){
                i--;
            }
            if (i==0){
                allCanUse[index]=-allCanUse[index];;
                return Math.abs(allCanUse[index]);
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(getPermutation1(3, 3));
    }
}
